5  Informed Search

Informed search strategies

  • Informed (heuristic) search strategies
    • Use problem-specific knowledge beyond the definition of the problem itself.
    • Can find solutions more efficiently than an uninformed strategy.

What is a heuristic?

  • Additional knowledge of the problem imparted to the search algorithm.
  • A heuristic estimates how close a state is to a goal.

5.5 Heuristic functions

The effect of heuristic accuracy on performance

  • Effective branching factor b^{*} characterizes the quality of a heuristic.
  • If the total number of nodes generated by A* for a particular problem is N and the solution depth is d, then b^{*} is the branching factor that a uniform tree of depth d would have to have in order to contain N+1 nodes: N+1=1+\left(b^{*}\right)+\left(b^{*}\right)^{2}+...+\left(b^{*}\right)^{d}
  • b^{*} varies across problem instances, but is fairly constant for sufficiently hard problems.
  • A well-designed heuristic would have a value of b^{*} close to 1 \Rightarrow fairly large problems solved at reasonable cost.
Comparison of the search costs and effective branching factors for the IDS and A* algorithms with h_{1}, h_{2}. Data are averaged over 100 instances of the 8-puzzle for each of various solution lengths d.
d IDS A*(h_{1}) A*(h_{2}) IDS A*(h_{1}) A*(h_{2})
2 10 6 6 2.45 1.79 1.79
4 112 13 12 2.87 1.48 1.45
6 680 20 18 2.73 1.34 1.30
8 6384 39 25 2.80 1.33 1.24
10 47127 93 39 2.79 1.38 1.22
12 3644035 227 73 2.78 1.42 1.24
14 539 113 1.44 1.23
16 1301 211 1.45 1.25
18 3056 363 1.46 1.26
20 7276 676 1.47 1.27
22 18094 1219 1.48 1.28
24 39135 1641 1.48 1.26

Dominance and Composite

  • If h_{2}(n)\geq h_{1}(n) for all n (both admissible), then h_{2} dominates h_{1} and is better for search.
    • A* using h_{2} will never expand more nodes than A* using h_{1}.
  • Hence, it is generally better to use a heuristic function with higher values, provided it is consistent and that the computation time for the heuristic is not too long.
  • Suppose a collection of admissible heuristics {h_{1},...,h_{m}} is available for a problem and none of them dominates any of the others.
  • The composite heuristic function is defined as h(n)=\max\{h_{1}(n),...,h_{m}(n)\}. It is consistent and dominates all component heuristics.

Relaxed problems

Definition

A problem with fewer restrictions on the actions is called a relaxed problem.

  • Prove that the angle in a semicircle is a right angle.

Generating admissible heuristics from relaxed problems

  • The state-space graph of the relaxed problem is a supergraph of the original state space because the removal of restrictions creates added edges in the graph.

  • Original problem state-space:

  • Relaxed problem state-space:

  • Hence, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.

  • Furthermore, because the derived heuristic is an exact cost for the relaxed problem, it must obey the triangle inequality and is therefore consistent.

Original problem of 8 puzzle

A tile can move from square A to square B if A is horizontally or vertically adjacent to B and B is blank.

We can generate three relaxed problems by removing one or both of the conditions:

Relaxed problems

  1. A tile can move from square A to square B if A is adjacent to B \to h_{2}.
  2. A tile can move from square A to square B if B is blank \to exercise.
  3. A tile can move from square A to square B \to h_{1}.

Generating admissible heuristics from subproblems

  • Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem.
    • The cost of the optimal solution of this subproblem \leq the cost of the original problem (lower bound).
    • It can be more accurate than Manhattan distance in some cases.
  • A subproblem of the 8-puzzle instance. The task is to get tiles 1, 2, 3, and 4 into their correct positions, without worrying about what happens to the other tiles.

Goal fixed?

  • Assume that the goal state G is fixed:

  • Using to find the shortest path from G to the other states:

  • The final g values can be considered as optimal h^{\ast} values:

Pattern databases

  • Pattern databases (PDB) store the exact solution costs for every possible subproblem instance.
    • E.g., every possible configuration of the four tiles and the blank.
  • The database itself is constructed by searching back from the goal and recording the cost of each new pattern encountered; the expense of this search is amortized over many subsequent problem instances.
  • The complete heuristic is constructed using the patterns in the databases.

Computing the Heuristic

  • 31 moves needed to solve red tiles.
  • 22 moves need to solve blue tiles.
  • Overall heuristic is maximum of 31=\max(31,22) moves.

Disjoint pattern databases

  • Limitation of traditional PDB: Taking the max \to diminishing returns on additional PDBs.
  • Disjoint pattern databases: Count only moves of the pattern tiles, ignoring non-pattern moves.
  • If no tile belongs to more than one pattern, add their heuristic values.

Computing the Heuristic

  • 20 moves needed to solve red tiles.
  • 25 moves needed to solve blue tiles.
  • Overall heuristic is sum, or 45=20+25 moves.

Performance

  • 15 Puzzle
    • 1000 \times speedup vs. Manhattan distance.
    • IDA* with the two DBs (the 7-tile database contains 58 million entries and the 8-tile database contains 519 million entries) solves 15-puzzles optimally in 30 milliseconds.
  • 24 Puzzle
    • 12 million \times speedup vs. Manhattan distance.
    • IDA* can solve random instances in 2 days.
    • Requires 4 DBs (each DB has 128 million entries).
    • Without PDBs: 65,000 years.

Learning heuristics from experience

  • Experience means solving a lot of instances of a problem.
    • E.g., solving lots of 8-puzzles.
  • Each optimal solution to a problem instance provides examples from which h(n) can be learned.
  • Learning algorithms:
    • Neural nets
    • Decision trees
    • Inductive learning

5.6 References